<!DOCTYPE html>
<html lang="zh-CN">
<!--浏览器搞笑标题-->
<script type="text/javascript" src="/js/FunnyTitle.js"></script>






<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/binblog/img/binblog.ico">
  <link rel="icon" type="image/png" href="/binblog/img/binblog.ico">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="">
  <meta name="author" content="leo-bin">
  <meta name="keywords" content="">
  <title>如何设计一个抢红包算法 - 阿斌的个人博客</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/binblog/lib/hint/hint.min.css" />

  
    <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/dracula.min.css" />
  

  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_yg9cfy8wd6.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_pjno9b9zyxs.css">


<link  rel="stylesheet" href="/binblog/css/main.css" />

<!-- 自定义样式保持在最底部 -->


<meta name="generator" content="Hexo 4.2.1"></head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/binblog/">&nbsp;<strong>Abin的Blog</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/binblog/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/binblog/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/binblog/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/binblog/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/binblog/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="view intro-2" id="background" parallax=true
         style="background: url('/binblog/img/6.webp') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container text-center white-text fadeInUp">
            <span class="h2" id="subtitle">
              
            </span>

            
              
  <div class="mt-3 post-meta">
    <i class="iconfont icon-date-fill" aria-hidden="true"></i>
    <time datetime="2020-05-30 22:39">
      2020年5月30日 晚上
    </time>
  </div>


<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      1.9k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      23
       分钟
    </span>
  

  
  
    
      <!-- LeanCloud 统计文章PV -->
      <span id="leancloud-post-views-container" class="post-meta" style="display: none">
        <i class="iconfont icon-eye" aria-hidden="true"></i>
        <span id="leancloud-post-views"></span> 次
      </span>
    
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <div class="post-content mx-auto" id="post">
            
              <p class="note note-info">
                
                  本文最后更新于：2020年7月31日 下午
                
              </p>
            
            <article class="markdown-body">
              <h1 id="抢红包算法"><a href="#抢红包算法" class="headerlink" title="抢红包算法"></a>抢红包算法</h1><blockquote>
<p>你会的越多，你不会的就越多，学无止境呀！</p>
</blockquote>
<h2 id="1-背景"><a href="#1-背景" class="headerlink" title="1.背景"></a>1.背景</h2><p><img src="https://bins-pic.oss-cn-shanghai.aliyuncs.com/mypic/红包.jpg" srcset="/binblog/img/loading.gif" alt=""></p>
<p><strong>自从微信红包上线以来，电子红包这个概念瞬间火遍大江南北</strong></p>
<p><strong>不仅身边的朋友成迷于电子红包，自己的家族群里也是。。。</strong></p>
<p><strong>一到过年，群里也不聊天，就等着抢红包。</strong></p>
<p><strong>怪不得说年味变了呢    </strong> <strong><code>╮(╯▽╰)╭</code></strong></p>
<h2 id="2-突发奇想"><a href="#2-突发奇想" class="headerlink" title="2.突发奇想"></a>2.突发奇想</h2><p>电子红包这么火，可是你知道它的设计原理吗？这么多人抢如何保证竞争的公平呢？</p>
<p>假设现在让你去设计一个抢红包的算法，你会怎么设计？</p>
<p><br></p>
<p><strong>要求：</strong></p>
<div class="hljs"><pre><code class="hljs tex">1.实现一个简单的分红包算法。
2.例如一个人在群里发了一个100块钱的红包，群里有10个人同时抢红包.
3.每个人抢到的金额完全随机。
4.要求所有人抢到的金额总数等于红包金额，不能多也不能少。
5.每个人抢到的红包金额不得低于0.01元。
6.要保证红包拆分的金额尽可能的分布均衡，不能出现两极分化这么严重的情况。</code></pre></div>
<p><br></p>
<h3 id="题外话"><a href="#题外话" class="headerlink" title="题外话"></a>题外话</h3><p>在我们正式开始动手之前我想提一个问题</p>
<p>先不管我们的算法是怎么设计的，我很好奇，这么多人，同时去抢一个红包，如何保证数据的一致性的?</p>
<p>我的第一想法是，应该是在塞红包的时候就已经将所有红包全都算了出来，然后写队列。</p>
<p>在开始抢的时候，只要去队列中消费已经提前分配好的红包就行。</p>
<p>但是经过一番查阅资料，在这里我可以告诉你，微信内部的实现恰恰相反！</p>
<p>他们就是在抢的时候实时算出来的 ！通过纯内存的计算，实时效率其实很高！</p>
<p>具体大家可以参考这片文章：  <strong><a href="https://www.zybuluo.com/yulin718/note/93148" target="_blank" rel="noopener">https://www.zybuluo.com/yulin718/note/93148</a></strong></p>
<h2 id="3-设计之前的思考"><a href="#3-设计之前的思考" class="headerlink" title="3.设计之前的思考"></a>3.设计之前的思考</h2><p>首先，这道题本质上就是一个<strong>分配问题</strong>！</p>
<p>无非就是，100个苹果如何公平的分给10个人？</p>
<p>那么要想保证分配的公平，随机呗！所以，一种解决方案就是使用随机数！</p>
<p><br></p>
<p><strong>科普：</strong></p>
<div class="hljs"><pre><code class="hljs xml">1.在Java中，jdk为我们提供了一个很方便的随机数生成api，那就是Random。
2.Random.nextInt(a)表示返回一个从0到a的随机int数。</code></pre></div>
<p><br></p>
<p>也就是说，我们只要确定这个a，那么红包的金额也就迎刃而解了！</p>
<p>但是我们如何确定这个a呢？一种非常直白的做法就是，a=[0.01，剩余金额-0.01]</p>
<p><strong>写成公式就是：</strong></p>
<script type="math/tex; mode=display">
[0.01,m-0.01]</script><p><br></p>
<p>也就是说，假设红包金额是100，5个人抢。</p>
<p>第一个人的随机范围就是：[0.01,99.99]。</p>
<p>他要从这个范围里面随机分配一个数字，假设是20。</p>
<p>那么第二个人的随机范围就是：[0.01,79.99]</p>
<p><strong>剩下的依次类推</strong>。。。。。。</p>
<p><br></p>
<p>乍一看，好像没啥问题，但是你稍微思考一下就会发现，这个算法非常的<strong>不公平</strong>！</p>
<p>因为越到后面的人，获取金额的随机范围会越来越小！反而是先抢的人，抢到大额红包的几率要大！</p>
<p>通过分析就可以知道，这个算法的缺点就是，他每一次的随机范围是递减的！</p>
<p>也就是说每一个人的随机分配范围是不一样的！</p>
<p><br></p>
<p>基于这一点，我们只要解决，每一次分配的随机范围的<strong>平均值</strong>是一样的就行！</p>
<p>经过查阅资料，其实可以采用一种叫做<strong><code>二倍均值</code></strong>的方式解决这个问题！</p>
<h2 id="4-二倍均值法"><a href="#4-二倍均值法" class="headerlink" title="4.二倍均值法"></a>4.二倍均值法</h2><h3 id="4-1思想"><a href="#4-1思想" class="headerlink" title="4.1思想"></a>4.1思想</h3><p>经过改良之后我们的<strong>随机范围公式</strong>等于：</p>
<script type="math/tex; mode=display">
[0.01,（m/n）*2-0.01]</script><p><br></p>
<p><strong>注：</strong></p>
<p><strong>其中m是剩余的金额，n是剩余的人数</strong></p>
<p><br></p>
<p><strong>还是之前的那个用例，假设m初始值=100，n=5</strong></p>
<p><br></p>
<p><strong>1.第一个人的随机范围就是：</strong></p>
<div class="hljs"><pre><code class="hljs xml">[0.01,（100/5）x2-0.01]，也就是：[0.01,39.99]，假设他抢了20</code></pre></div>
<p><strong>2.那么第二个人的随机范围就是：</strong></p>
<div class="hljs"><pre><code class="hljs xml">[0.01,（80/4）*2-0.01]，那就是，[0.01,39.99]，假设他也抢了20</code></pre></div>
<p><strong>3.那么第三个人就是：</strong></p>
<div class="hljs"><pre><code class="hljs hxml">[0.01,（60&#x2F;3）*2-0.01]，就是，[0.01,39.99]，假设他也抢了20</code></pre></div>
<p><strong>以此类推。。。。。你会发现，每一个人能够抢到的金额的平均值都是20！</strong></p>
<p><br></p>
<h3 id="4-2细节"><a href="#4-2细节" class="headerlink" title="4.2细节"></a>4.2细节</h3><p><strong>1）关于精度的细节：</strong></p>
<p>首先对于金钱类问题我们不可能使用整形来做为基本单位，一般都是double。</p>
<p>这里用到了一种特殊的对象专门用来处理高精度的情况，它就是<strong>BigDecimal。</strong></p>
<p><br></p>
<p><strong>具体用法：</strong></p>
<p>假设这里我们给一个：<strong>double value=25.555555</strong></p>
<p>我们希望将它<strong>保留2位小数</strong>，那我们可以这么做：</p>
<div class="hljs"><pre><code class="hljs java">BigDecimal bigDecimal = <span class="hljs-keyword">new</span> BigDecimal(Double.toString(value));
bigDecimal.setScale(<span class="hljs-number">2</span>, BigDecimal.ROUND_HALF_UP).doubleValue();</code></pre></div>
<p><strong>解释：</strong></p>
<p><strong>1.这里的setScale方法就是保留小数，2代表保留2位小数。</strong></p>
<p><strong>2.BigDecimal.ROUND_HALF_UP表示四舍五入。</strong></p>
<p><br></p>
<p><strong>2）关于具体算法的细节：</strong></p>
<p>在数学中我们可以可以很轻松的表示出上面的那个<strong>随机范围公式</strong>：</p>
<script type="math/tex; mode=display">
[0.01,(m/n)*2-0.01]</script><p>但是我们如何使用代码实现？</p>
<p><br></p>
<p><strong>为了便于我们理解，我们简化一下公式：</strong></p>
<script type="math/tex; mode=display">
[start,end]</script><p><br></p>
<p><strong>所以问题就是如何求start到end中间的某个随机数！</strong></p>
<p><br></p>
<p><strong>我们可以使用下面这个公式实现：</strong></p>
<script type="math/tex; mode=display">
random=start+Math.random()*(end-start)</script><p><br></p>
<p><strong>关于Math.random()：</strong></p>
<p>它返回的是一个在<strong>[0,1.0]</strong>之间的double值！</p>
<p>假设m就是restMoney，n就是restPeople，那么</p>
<p>0.01就是start，end就是：<strong>restMoney/restPeople*2</strong></p>
<p>double random = 0.01 + Math.random() <em> (restMoney  / restPeople </em> 2 - 0.01)</p>
<h2 id="5-代码实现"><a href="#5-代码实现" class="headerlink" title="5.代码实现"></a>5.代码实现</h2><p><strong>在知道了具体的随机分配公式以及如何保留精度之后，剩下的就非常简单了！</strong></p>
<p><strong>直接上代码！</strong></p>
<p><br></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> List&lt;Double&gt; <span class="hljs-title">divideRedPacket</span><span class="hljs-params">(Double totalMoney, Integer totalPeople)</span> </span>&#123;
    List&lt;Double&gt; moneyList = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;();
    <span class="hljs-keyword">double</span> restMoney = totalMoney;
    <span class="hljs-keyword">int</span> restPeople = totalPeople;
    <span class="hljs-comment">//只算前面total-1个人，最后一个人不算</span>
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; totalPeople - <span class="hljs-number">1</span>; i++) &#123;
        <span class="hljs-comment">//[0.01,m/n*2-0.01]</span>
        <span class="hljs-keyword">double</span> currentMoney = getRandomMoney(restMoney, restPeople, <span class="hljs-number">2</span>);
        restMoney -= currentMoney;
        restPeople--;
        moneyList.add(currentMoney);
    &#125;
    <span class="hljs-comment">//最后一人就不用算随机数了，直接将剩下的钱都给他就行</span>
    moneyList.add(getDoubleByScale(<span class="hljs-number">2</span>, restMoney));
    <span class="hljs-keyword">return</span> moneyList;
&#125;

<span class="hljs-comment">/**</span>
<span class="hljs-comment"> * 获取某个范围内的随机double值</span>
<span class="hljs-comment"> *</span>
<span class="hljs-comment"> * <span class="hljs-doctag">@param</span> restMoney  剩余的钱</span>
<span class="hljs-comment"> * <span class="hljs-doctag">@param</span> restPeople 剩余的人数</span>
<span class="hljs-comment"> * <span class="hljs-doctag">@param</span> scale      保留精度</span>
<span class="hljs-comment"> */</span>
<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">double</span> <span class="hljs-title">getRandomMoney</span><span class="hljs-params">(<span class="hljs-keyword">double</span> restMoney, <span class="hljs-keyword">int</span> restPeople, <span class="hljs-keyword">int</span> scale)</span> </span>&#123;
    <span class="hljs-keyword">double</span> random = <span class="hljs-number">0.01</span> + Math.random() * (restMoney / restPeople * <span class="hljs-number">2</span> - <span class="hljs-number">0.01</span>);
    <span class="hljs-keyword">return</span> getDoubleByScale(scale, random);
&#125;

<span class="hljs-comment">/**</span>
<span class="hljs-comment"> * 根据精度返回double值</span>
<span class="hljs-comment"> */</span>
<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">double</span> <span class="hljs-title">getDoubleByScale</span><span class="hljs-params">(<span class="hljs-keyword">int</span> scale, <span class="hljs-keyword">double</span> value)</span> </span>&#123;
    BigDecimal bigDecimal = <span class="hljs-keyword">new</span> BigDecimal(Double.toString(value));
    <span class="hljs-keyword">return</span> bigDecimal.setScale(scale, BigDecimal.ROUND_HALF_UP).doubleValue();
&#125;</code></pre></div>
<h2 id="6-测试"><a href="#6-测试" class="headerlink" title="6.测试"></a>6.测试</h2><p><strong>1.假设我们发一个金额为100的红包。</strong></p>
<p><strong>2.并规定有10个人同时抢。</strong></p>
<p><strong>3.测试代码和结果如下。</strong></p>
<h3 id="6-1测试代码"><a href="#6-1测试代码" class="headerlink" title="6.1测试代码"></a>6.1测试代码</h3><div class="hljs"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
    <span class="hljs-keyword">double</span> money = <span class="hljs-number">100.0</span>;
    <span class="hljs-keyword">int</span> people = <span class="hljs-number">10</span>;
    List&lt;Double&gt; result = divideRedPacket(money, people);
    <span class="hljs-keyword">if</span> (result != <span class="hljs-keyword">null</span> &amp;&amp; result.size() &gt; <span class="hljs-number">0</span>) &#123;
        <span class="hljs-keyword">double</span> sum = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; result.size(); i++) &#123;
            System.out.println(<span class="hljs-string">"第"</span> + (i + <span class="hljs-number">1</span>) + <span class="hljs-string">"个人抢到了："</span> + result.get(i) + <span class="hljs-string">"元"</span>);
            sum += result.get(i);
        &#125;
        System.out.println(<span class="hljs-string">"红包总金额是："</span> + sum + <span class="hljs-string">",共有"</span> + people + <span class="hljs-string">"个人抢"</span>);
    &#125;
&#125;</code></pre></div>
<h3 id="6-2测试结果"><a href="#6-2测试结果" class="headerlink" title="6.2测试结果"></a>6.2测试结果</h3><p><img src="https://bins-pic.oss-cn-shanghai.aliyuncs.com/mypic/测试结果.jpg" srcset="/binblog/img/loading.gif" alt=""></p>
<h2 id="7-总结"><a href="#7-总结" class="headerlink" title="7.总结"></a>7.总结</h2><p><strong>1.其实这么一个看似很复杂的问题通过我们这么层层分析，到最后其实是非常简单的。</strong></p>
<p><strong>2.难点就在于如何写出可维护性，易读性的代码。</strong></p>
<p><strong>3.还有最后关于精度的处理，我在没有接触到这个算法之前就是不知道还可以这么处理double</strong></p>
<h2 id="参考"><a href="#参考" class="headerlink" title="参考"></a>参考</h2><p>1.<a href="https://blog.csdn.net/bjweimengshu/article/details/80045958" target="_blank" rel="noopener">https://blog.csdn.net/bjweimengshu/article/details/80045958</a></p>
<p>2.<a href="https://www.zybuluo.com/yulin718/note/93148" target="_blank" rel="noopener">https://www.zybuluo.com/yulin718/note/93148</a></p>
<p>3.<a href="https://www.zhihu.com/question/22625187" target="_blank" rel="noopener">https://www.zhihu.com/question/22625187</a></p>

            </article>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/binblog/categories/%E7%AE%97%E6%B3%95/">算法</a>
                    
                  </div>
                
                
              </div>
              
                <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" target="_blank" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！</p>
              
              
                <div class="post-prevnext row">
                  <div class="post-prev col-6">
                    
                    
                      <a href="/binblog/2020/05/31/%E5%A6%82%E4%BD%95%E4%BD%BF%E7%94%A8Java%E8%AE%BE%E8%AE%A1%E4%B8%80%E4%B8%AA%E7%94%9F%E4%BA%A7%E8%80%85%E6%B6%88%E8%B4%B9%E8%80%85/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">如何用Java设计一个简单的生产者消费者</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </div>
                  <div class="post-next col-6">
                    
                    
                      <a href="/binblog/2020/05/30/hello-world/">
                        <span class="hidden-mobile">Hello World</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </div>
                </div>
              
            </div>

            
              <!-- Comments -->
              <div class="comments" id="comments">
                
                
  <div id="vcomments"></div>
  <script defer src="https://cdn.staticfile.org/valine/1.4.14/Valine.min.js" ></script>

  <script type="text/javascript">
    var oldLoadVa = window.onload;
    window.onload = function () {
      oldLoadVa && oldLoadVa();

      new Valine({
        el: "#vcomments",
        app_id: "vsanVmkaurLHyq2Xey9odo5V-gzGzoHsz",
        app_key: "v2hMMe4Mzz3mqpy9jwd7qx8B",
        placeholder: "说点什么吧！",
        path: window.location.pathname,
        avatar: "retro",
        meta: ["nick","mail","link"],
        pageSize: "10",
        lang: "zh-CN",
        highlight: true,
        recordIP: false,
        serverURLs: "",
      });
    };
  </script>
  <noscript>Please enable JavaScript to view the <a href="https://valine.js.org" target="_blank" rel="nofollow noopener noopener">comments
      powered by Valine.</a></noscript>


              </div>
            
          </div>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  

  

  <footer class="mt-5">
  <div class="text-center py-3">
    <div>
      <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a>
      <i class="iconfont icon-love"></i>
      <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener">
        <span>Fluid</span></a>
    </div>
    
  <div class="statistics">
    
    

    
      
        <!-- LeanCloud 统计PV -->
        <span id="leancloud-site-pv-container" style="display: none">
            总访问量 
            <span id="leancloud-site-pv"></span>
             次
          </span>
      
      
        <!-- LeanCloud 统计UV -->
        <span id="leancloud-site-uv-container" style="display: none">
            总访客数 
            <span id="leancloud-site-uv"></span>
             人
          </span>
      

    
  </div>


    
  <!-- 备案信息 -->
  <div class="beian">
    <a href="http://beian.miit.gov.cn/" target="_blank"
       rel="nofollow noopener">京ICP证123456号</a>
    
      <a
        href="http://www.beian.gov.cn/portal/registerSystemInfo?recordcode=12345678"
        rel="nofollow noopener"
        class="beian-police"
        target="_blank"
      >
        <span class="beian-police-sep">&nbsp;|&nbsp;</span>
        
          <img src="/binblog/img/police_beian.png" srcset="/binblog/img/loading.gif" alt="police-icon" />
        
        <span>京公网安备12345678号</span>
      </a>
     
  </div>


    
  </div>
</footer>

<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/binblog/js/debouncer.js" ></script>
<script  src="/binblog/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/binblog/js/lazyload.js" ></script>
  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/binblog/js/clipboard-use.js" ></script>



  <script defer>
  (function () {
    // 查询存储的记录
    function getRecord(Counter, target) {
      return new Promise(function (resolve, reject) {
        Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({target})))
          .then(resp => resp.json())
          .then(({results, code, error}) => {
            if (code === 401) {
              throw error;
            }
            if (results && results.length > 0) {
              var record = results[0];
              resolve(record);
            } else {
              Counter('post', '/classes/Counter', {target, time: 0})
                .then(resp => resp.json())
                .then((record, error) => {
                  if (error) {
                    throw error;
                  }
                  resolve(record);
                }).catch(error => {
                console.error('Failed to create', error);
                reject(error);
              });
            }
          }).catch((error) => {
          console.error('LeanCloud Counter Error:', error);
          reject(error);
        });
      })
    }

    // 发起自增请求
    function increment(Counter, incrArr) {
      return new Promise(function (resolve, reject) {
        Counter('post', '/batch', {
          "requests": incrArr
        }).then((res) => {
          res = res.json();
          if (res.error) {
            throw res.error;
          }
          resolve(res);
        }).catch((error) => {
          console.error('Failed to save visitor count', error);
          reject(error);
        });
      });
    }

    // 构建自增请求体
    function buildIncrement(objectId) {
      return {
        "method": "PUT",
        "path": `/1.1/classes/Counter/${ objectId }`,
        "body": {
          "time": {
            '__op': 'Increment',
            'amount': 1
          }
        }
      }
    }

    // 校验是否为有效的 UV
    function validUV() {
      var key = 'LeanCloud_UV_Flag';
      var flag = localStorage.getItem(key);
      if (flag) {
        // 距离标记小于 24 小时则不计为 UV
        if (new Date().getTime() - parseInt(flag) <= 86400000) {
          return false;
        }
      }
      localStorage.setItem(key, new Date().getTime().toString());
      return true;
    }

    function addCount(Counter) {
      var enableIncr = 'true' === 'true' && window.location.hostname !== 'localhost';
      var getterArr = [];
      var incrArr = [];

      // 请求 PV 并自增
      var pvCtn = document.querySelector('#leancloud-site-pv-container');
      if (pvCtn || enableIncr) {
        var pvGetter = getRecord(Counter, 'site-pv').then((record) => {
          incrArr.push(buildIncrement(record.objectId))
          var ele = document.querySelector('#leancloud-site-pv');
          if (ele) {
            ele.innerText = record.time + 1;
            if (pvCtn) {
              pvCtn.style.display = 'inline';
            }
          }
        });
        getterArr.push(pvGetter);
      }

      // 请求 UV 并自增
      var uvCtn = document.querySelector('#leancloud-site-uv-container');
      if (uvCtn || enableIncr) {
        var uvGetter = getRecord(Counter, 'site-uv').then((record) => {
          var vuv = validUV();
          vuv && incrArr.push(buildIncrement(record.objectId))
          var ele = document.querySelector('#leancloud-site-uv');
          if (ele) {
            ele.innerText = record.time + (vuv ? 1 : 0);
            if (uvCtn) {
              uvCtn.style.display = 'inline';
            }
          }
        });
        getterArr.push(uvGetter);
      }

      // 如果是文章，请求文章的浏览数，并自增
      if ('true' === 'true') {
        var viewCtn = document.querySelector('#leancloud-post-views-container');
        if (viewCtn || enableIncr) {
          var target = decodeURI('/binblog/2020/05/30/%E8%AE%BE%E8%AE%A1%E4%B8%80%E4%B8%AA%E6%8A%A2%E7%BA%A2%E5%8C%85%E7%AE%97%E6%B3%95/');
          var viewGetter = getRecord(Counter, target).then((record) => {
            incrArr.push(buildIncrement(record.objectId))
            if (viewCtn) {
              var ele = document.querySelector('#leancloud-post-views');
              if (ele) {
                ele.innerText = (record.time || 0) + 1;
                viewCtn.style.display = 'inline';
              }
            }
          });
          getterArr.push(viewGetter);
        }
      }

      // 如果启动计数自增，批量发起自增请求
      if (enableIncr) {
        Promise.all(getterArr).then(() => {
          incrArr.length > 0 && increment(Counter, incrArr);
        })
      }
    }

    var app_id = 'vsanVmkaurLHyq2Xey9odo5V-gzGzoHsz'
    var app_key = 'v2hMMe4Mzz3mqpy9jwd7qx8B'
    var server_url = ''

    function fetchData(api_server) {
      var Counter = (method, url, data) => {
        return fetch(`${ api_server }/1.1${ url }`, {
          method,
          headers: {
            'X-LC-Id': app_id,
            'X-LC-Key': app_key,
            'Content-Type': 'application/json',
          },
          body: JSON.stringify(data)
        });
      };

      addCount(Counter);
    }

    var api_server = app_id.slice(-9) !== '-MdYXbMMI' ? server_url : `https://${ app_id.slice(0, 8).toLowerCase() }.api.lncldglobal.com`;

    if (api_server) {
      fetchData(api_server);
    } else {
      fetch('https://app-router.leancloud.cn/2/route?appId=' + app_id)
        .then(resp => resp.json())
        .then(({api_server}) => {
          fetchData('https://' + api_server);
        });
    }
  })();
</script>






  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: 'article.markdown-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 0,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "如何设计一个抢红包算法&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 70,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script  src="https://cdn.staticfile.org/anchor-js/4.2.2/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "hover",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script  src="/binblog/js/local-search.js" ></script>
  <script>
    var path = "/binblog/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>





  

  
    <!-- MathJax -->
    <script>
      MathJax = {
        tex: {
          inlineMath: [['$', '$'], ['\\(', '\\)']]
        },
        options: {
          renderActions: {
            findScript: [10, doc => {
              document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
                const display = !!node.type.match(/; *mode=display/);
                const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
                const text = document.createTextNode('');
                node.parentNode.replaceChild(text, node);
                math.start = { node: text, delim: '', n: 0 };
                math.end = { node: text, delim: '', n: 0 };
                doc.math.push(math);
              });
            }, '', false],
            insertedScript: [200, () => {
              document.querySelectorAll('mjx-container').forEach(node => {
                let target = node.parentNode;
                if (target.nodeName.toLowerCase() === 'li') {
                  target.parentNode.classList.add('has-jax');
                }
              });
            }, '', false]
          }
        }
      };
    </script>

    <script async src="https://cdn.staticfile.org/mathjax/3.0.5/es5/tex-svg.js" ></script>

  













  

  

  

  

  

  





<script src="/binblog/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"model":{"jsonPath":"/binblog/live2dw/assets/koharu.model.json"},"display":{"position":"right","width":150,"height":300},"mobile":{"show":true},"log":false,"pluginJsPath":"lib/","pluginModelPath":"assets/","pluginRootPath":"live2dw/","tagMode":false});</script></body>
</html>
